/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

/**
 * <p>数组可能重复，查找在旋转数组中的最小元素</p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月21日
 */
public class FindMinimumInRotatedSortedArrayII {

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        int mid = 0;
        int min = nums[left];
        while(left<right){
            mid = left+(right-left)/2;
            min = Math.min(nums[left], min);
            if(nums[mid]==nums[left] && nums[mid] == nums[right]){
                //不确定最小值在哪一个部分，向前移动一格
                left++;
            }else if(nums[mid]>=nums[left]){
                //在右边进行查找
                left = mid+1;
                min = Math.min(nums[left], min);
            }else{
                //在左半部分进行查找哦
                min = Math.min(nums[mid], min);
                right = mid-1;
            }
        }
        return min;
    }
}
